'''
二叉搜索树
    二叉搜索树是一棵二叉树且满足性质:设x是二叉树的一个节点.如果y是x 左子树的一个节点,那么y.key<=x.key;
    如果y是x右子树的一个节点,那么y.key>=x.key.
    二叉搜索树的操作:查询,插入.删除

    二叉树删除操作:
        1.如果要删除的结点是叶子结点:直接删除
        2.如果要删除的结点只有一个孩子:将此节点的父亲与孩子连接,然后删除该结点
        3.如果要删除的结点有两个孩子:将其右子树的最小节点(该结点最多有一个右孩子)删除,并替换当前节点
'''

'''
# 二叉树节点类
class BiTreeNode:
    # 节点构造函数
    def __init__(self, data):
        self.data = data  # 节点存储的数据值
        self.lchild = None  # 左子节点指针（初始为空）
        self.rchild = None  # 右子节点指针（初始为空）
        self.parent = None  # 父节点指针（初始为空）


# 二叉搜索树类
class BST:
    # BST构造函数
    def __init__(self, li=None):
        self.root = None  # 树的根节点（初始为空）
        # 如果提供了初始列表，按顺序插入所有元素
        if li:
            for val in li:
                self.insert_no_rec(val)  # 使用非递归方式插入元素

    # 递归插入方法（内部使用）
    def insert(self, node, val):
        # 基本情况：当前节点为空，创建新节点
        if not node:
            node = BiTreeNode(val)  # 创建值为val的新节点

        # 递归情况1：插入值小于当前节点值 → 向左子树插入
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)  # 递归调用左子树
            node.lchild.parent = node  # 设置左子节点的父指针

        # 递归情况2：插入值大于当前节点值 → 向右子树插入
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)  # 递归调用右子树
            node.rchild.parent = node  # 设置右子节点的父指针

        # 注意：当val == node.data时不操作（BST不允许重复值）

        return node  # 返回修改后的节点（包含新的子树）

    # 非递归插入方法（公共接口）
    def insert_no_rec(self, val):
        p = self.root  # 从根节点开始遍历

        # 情况1：空树 → 直接创建根节点
        if not p:  # 空树检查
            self.root = BiTreeNode(val)  # 创建根节点
            return  # 插入完成

        # 情况2：非空树 → 寻找插入位置
        while True:
            # 向左子树查找插入位置
            if val < p.data:
                if p.lchild:  # 左子节点存在
                    p = p.lchild  # 向左移动
                else:  # 找到插入位置
                    p.lchild = BiTreeNode(val)  # 创建左子节点
                    p.lchild.parent = p  # 设置父指针
                    return  # 插入完成

            # 向右子树查找插入位置
            elif val > p.data:
                if p.rchild:  # 右子节点存在
                    p = p.rchild  # 向右移动
                else:  # 找到插入位置
                    p.rchild = BiTreeNode(val)  # 创建右子节点
                    p.rchild.parent = p  # 设置父指针
                    return  # 插入完成

            # 值已存在 → 不插入（BST不允许重复）
            else:
                return  # 不做操作

    def query_no_rec(self,val):
        p = self.root
        while p:
            if val < p.data:
                p = p.lchild
            elif val > p.data:
                p = p.rchild
            else:
                return p
        else:
            return None

    def query(self,node,val):
        if not node:
            return None
        if val < node.data:
            return self.query(node.lchild,val)
        elif val > node.data:
            return self.query(node.rcild,val)
        else:
            return node


    def pre_order(self,root):
        if root:
            print(root.data,end = ',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    def in_order(self,root):
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)

    def post_order(self,root):
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')

    def __remove_node_1(self,node):
        # 情况1,node是叶子结点
        if not node.parent:
            self.root = None
        if __name__ == '__main__':
            if node == node.parent.lchild: # node是它父亲的左孩子
                node.parent.lchild = None
            else: #如果是右孩子
                node.parent.rchild = None

    def __remove_node_2(self,node):
        # 情况2:node只有一个左孩子
        if not node.parent: #是根节点
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parient
        else:  # node是父节点的右孩子
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent

    def __remove_node_22(self,node):
        # 情况2.2,node只有一个右孩子
        if not node.parient:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent

    def delete(self,val):
        if self.root: # 不是空树
            node = self.query_no_rec(val)
            if not node: # 不存在
                return False
            if not node.lchild and not node.rchild:
                self.__remove_node_1(node)
            elif not node.rchild: #2.1只有一个左孩子
                self.__remove_node_2(node)
            elif not node.lchild: # 2.2 只有一个右孩子
                self.__remove_node_22(node)
            else:
                # 3.左右孩子都存在
                min_node = node.rchild
                while min_node.lchild:
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)

tree = BST([4,6,7,9,2,1,3,5,8])
tree.pre_order((tree.root))
print('')
tree.in_order((tree.root))
print('')
tree.post_order((tree.root))
print('')'''


class BiTreeNode:
    # 节点构造函数
    def __init__(self, data):
        self.data = data  # 节点存储的数据值
        self.lchild = None  # 左子节点指针（初始为空）
        self.rchild = None  # 右子节点指针（初始为空）
        self.parent = None  # 父节点指针（初始为空）


# 二叉搜索树类
class BST:
    # BST构造函数
    def __init__(self, li=None):
        self.root = None  # 树的根节点（初始为空）
        # 如果提供了初始列表，按顺序插入所有元素
        if li:
            for val in li:
                self.insert_no_rec(val)  # 使用非递归方式插入元素

    # 递归插入方法（内部使用）
    def insert(self, node, val):
        # 基本情况：当前节点为空，创建新节点
        if not node:
            node = BiTreeNode(val)  # 创建值为val的新节点

        # 递归情况1：插入值小于当前节点值 → 向左子树插入
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)  # 递归调用左子树
            node.lchild.parent = node  # 设置左子节点的父指针

        # 递归情况2：插入值大于当前节点值 → 向右子树插入
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)  # 递归调用右子树
            node.rchild.parent = node  # 设置右子节点的父指针

        # 注意：当val == node.data时不操作（BST不允许重复值）

        return node  # 返回修改后的节点（包含新的子树）

    # 非递归插入方法（公共接口）
    def insert_no_rec(self, val):
        p = self.root  # 从根节点开始遍历

        # 情况1：空树 → 直接创建根节点
        if not p:  # 空树检查
            self.root = BiTreeNode(val)  # 创建根节点
            return  # 插入完成

        # 情况2：非空树 → 寻找插入位置
        while True:
            # 向左子树查找插入位置
            if val < p.data:
                if p.lchild:  # 左子节点存在
                    p = p.lchild  # 向左移动
                else:  # 找到插入位置
                    p.lchild = BiTreeNode(val)  # 创建左子节点
                    p.lchild.parent = p  # 设置父指针
                    return  # 插入完成

            # 向右子树查找插入位置
            elif val > p.data:
                if p.rchild:  # 右子节点存在
                    p = p.rchild  # 向右移动
                else:  # 找到插入位置
                    p.rchild = BiTreeNode(val)  # 创建右子节点
                    p.rchild.parent = p  # 设置父指针
                    return  # 插入完成

            # 值已存在 → 不插入（BST不允许重复）
            else:
                return  # 不做操作

    def query_no_rec(self, val):
        p = self.root
        while p:
            if val < p.data:
                p = p.lchild
            elif val > p.data:
                p = p.rchild
            else:
                return p
        else:
            return None

    def query(self, node, val):
        if not node:
            return None
        if val < node.data:
            return self.query(node.lchild, val)
        elif val > node.data:
            # 修复拼写错误：rcild → rchild
            return self.query(node.rchild, val)
        else:
            return node

    def pre_order(self, root):
        if root:
            print(root.data, end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    def in_order(self, root):
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)

    def post_order(self, root):
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')

    def __remove_node_1(self, node):
        # 情况1: node是叶子结点
        if not node.parent:
            self.root = None
        # 移除错误的__main__判断
        if node == node.parent.lchild:  # node是它父亲的左孩子
            node.parent.lchild = None
        else:  # 如果是右孩子
            node.parent.rchild = None

    def __remove_node_2(self, node):
        # 情况2: node只有一个左孩子
        if not node.parent:  # 是根节点
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:
            node.parent.lchild = node.lchild
            # 修复拼写错误：parient → parent
            node.lchild.parent = node.parent
        else:  # node是父节点的右孩子
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent

    def __remove_node_22(self, node):
        # 情况2.2: node只有一个右孩子
        # 修复拼写错误：parient → parent
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent

    def delete(self, val):
        if self.root:  # 不是空树
            node = self.query_no_rec(val)
            if not node:  # 不存在
                return False
            if not node.lchild and not node.rchild:
                self.__remove_node_1(node)
            elif not node.rchild:  # 2.1 只有一个左孩子
                self.__remove_node_2(node)
            elif not node.lchild:  # 2.2 只有一个右孩子
                self.__remove_node_22(node)
            else:
                # 3. 左右孩子都存在
                min_node = node.rchild
                while min_node.lchild:
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)


# 测试代码
if __name__ == '__main__':
    tree = BST([4, 6, 7, 9, 2, 1, 3, 5, 8])
    print("前序遍历: ", end="")
    tree.pre_order(tree.root)
    print('\n')

    print("中序遍历: ", end="")
    tree.in_order(tree.root)
    print('\n')

    print("后序遍历: ", end="")
    tree.post_order(tree.root)
    print('\n')
